package ink.lovejinhu.leetcodeMatch;

/**
 * @author jinhu
 * created 2021-07-18 11:19
 */
public class Solution_5816 {
    public int[] maxGeneticDifference(int[] parents, int[][] queries) {
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int start = queries[i][0];
            int end = queries[i][1];
            int startParent = parents[start];
            int endParent = parents[end];
            if (startParent == -1) {
                res[i] = queries[i][1] ^ start;
            } else {
                if (endParent == -1) {
                    res[i] = queries[i][1] ^ end;
                } else {
                    while (startParent != endParent || start != endParent || end != startParent) {
                        if (parents[startParent] == -1) {
                            if (parents[endParent] == -1) {
                                break;
                            } else {
                                endParent = parents[endParent];
                            }
                        } else {
                            if (parents[endParent] == -1) {
                                startParent = parents[startParent];
                            } else {
                                startParent = parents[startParent];
                                endParent = parents[endParent];
                            }
                        }
                    }
                    res[i] = queries[i][1] ^ startParent;
                }
            }

        }
        return res;
    }
}
